public class Leetcode1139 {
    public int largest1BorderedSquare(int[][] grid) {
        int[][] upInfix = new int[grid.length][grid[0].length];
        int[][] leftInfix = new int[grid.length][grid[0].length];
        for (int r = 0; r < grid.length; r++) {
            int num = 0;
            for (int c = 0; c < grid[r].length; c++) {
                num += grid[r][c];
                leftInfix[r][c] = num;
            }
        }

        for (int c = 0; c < grid[0].length; c++) {
            int num = 0;
            for (int r = 0; r < grid.length; r++) {
                num += grid[r][c];
                upInfix[r][c] = num;
            }
        }

        //最大正方形的边长
        int max = Math.min(grid[0].length, grid.length);

        //从最大正方形的边长开始往小了找
        for (int i = max; i > 0; i--) {
            for (int r = 0; r <= grid.length - i; r++) {
                for (int c = 0; c <= grid[r].length - i; c++) {
//                  左上：[r][c]，    右上：[r][c+i-1]，
//                  左下：[r+i-1][c]，右下：[r+i-1][c+i-1]

                    //左上到左下不是条1的线
                    if (upInfix[r + i - 1][c] - upInfix[r][c] != i - 1 || grid[r][c] != 1) {
                        continue;
                    }

                    //右上到右下不是条1的线
                    if (upInfix[r + i - 1][c + i - 1] - upInfix[r][c + i - 1] != i - 1 || grid[r][c + i - 1] != 1) {
                        continue;
                    }

                    //左上到右上不是条1的线
                    if (leftInfix[r][c + i - 1] - leftInfix[r][c] != i - 1 || grid[r][c] != 1) {
                        continue;
                    }

                    //左下到右下不是条1的线
                    if (leftInfix[r + i - 1][c + i - 1] - leftInfix[r + i - 1][c] != i - 1 || grid[r + i - 1][c] != 1) {
                        continue;
                    }

                    return i * i;
                }
            }
        }

        return 0;
    }
}
